//一条包含字母 A-Z 的消息通过以下方式进行了编码： 
//
// 'A' -> 1
//'B' -> 2
//...
//'Z' -> 26
// 
//
// 给定一个只包含数字的非空字符串，请计算解码方法的总数。 
//
// 示例 1: 
//
// 输入: "12"
//输出: 2
//解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
// 
//
// 示例 2: 
//
// 输入: "226"
//输出: 3
//解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
// 
// Related Topics 字符串 动态规划

  
package com.gule.gl.leetcode.editor.cn;
public class DecodeWays{
    public static void main(String[] args) {
         Solution solution = new DecodeWays().new Solution();
         System.out.println(solution.numDecodings("0"));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int numDecodings(String s) {
        char[] chars = s.toCharArray();
        return decode(chars, chars.length -1);
    }
        //递归法解决
        private int decode(char[] chars, int index) {
            if(index == 0 && chars[0] == '0'){
                return 0;
            }
            if(index <= 0){
                return 1;
            }
            int count = 0;
            char current = chars[index];
            char pre = chars[index -1];
            if(current > '0'){
                count = decode(chars, index -1);
            }
            if(pre == '1' || (pre == '2' && current <= '6')){
                count += decode(chars, index - 2);
            }
            return count;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
